9-6 TkPpX

MATLAB 亦提供了一系列指令，可用來解決三角化（Triangulation）、鄰近點（Nearest Neighbors），及其它計算幾何（Computational Geometry）方面的問題，首先我們解釋何謂 Delaunay 三角化（Trangulation）。給定一組 X-Y 平面上的點，Delaunay 指令可傳回一組由這些點所形成的三角形，而且任一點均不會位於任一個三角形的外接圓之內。為展示 Delaunay 的用法，首先我們讀入一組 X-Y平面上的資料點，並以散佈圖的方式來表示：

Example 1: 09-內插法/seamount01.m

load seamount.mat plot(x, y, '.');

我們可對上述資料點進行 Delaunary 三角化，並使用 triplot 指令畫出其結果，再將原先的資料疊上去，例如：

Example 2: 09-內插法/triplot01.m

load seamount.mat tri = delaunay(x, y); triplot(tri, x, y); hold on, plot(x, y, '.r'); hold off

我們也可以使用 trisurf 或是 trimesh 來畫出使用三角內插所產生的曲面，如下：

Example 3: 09-內插法/trisurf01.m

load seamount.mat tri = delaunay(x, y); trisurf(tri, x, y, z); axis tight; colorbar

讀者可將上述範例中的 trisurf 改成 trimesh，就可以產生三角網狀曲面。若要產生等高線，就要使用之前提到的 griddata 指令，如下：

Example 4: 09-內插法/tricontour01.m

load seamount.mat xi = linspace(min(x), max(x), 50); yi = linspace(min(y), max(y), 50); [xi, yi] = meshgrid(xi, yi); zi = griddata (x, y, z, xi, yi, 'cubic'); [c, h] = contourf(xi, yi, zi, 'b-'); clabel (c, h); colorbar; % 顯示顏色與函數值的對照表

一旦完成 Delaunary 三角化之後，您可以進行兩種搜尋：

• dsearch 指令可找出一給定點的最鄰近資料點
• tsearch 指令可找出一給定點所在之三角形

Voronoi 圖形和 Delaunay 三角化關係非常密切，Voronoi 圖形可將資料點所在的平面畫分成數個多邊形，每一個多邊形只包含一個資料點，而且給定任一點時，此點和其最鄰近的資料點會落於同一個多邊形內。事實上，只要將 Delaunary 所得的各個三角形中，對每一邊畫出垂直平方線，即可得到 Voronoi 圖形。MATLAB 的 voronoi 指令可用來畫出 Voronoi 圖形，舉例如下：

Example 5: 09-內插法/voronoi01.m

load seamount.mat voronoi(x, y);

我們可將 Voronoi 圖形和 Delaunay 三角形畫在同一張圖，如下：

Example 6: 09-內插法/voronoi02.m

x = rand(20,1); y = rand(20,1); voronoi(x, y, 'b:'); tri = delaunay(x, y); hold on h = trimesh(tri, x, y, 0*x); hold off set(h, 'facecolor', 'none'); axis equal square axis([0 1 0 1]);

在上圖中，實線是 Delaunay 三角形，虛線則是 Voronoi 圖形。事實上，每一條 Voronoi 圖形的線段，都是某一個三角形的一邊的中垂線，所以每一個 Voronoi 圖形所形成的多邊形的頂點，都是某一個三角形的外心。此外，每一個 Voronoi 圖形所形成的多邊形，都只有包含一個取樣資料點，代表此取樣資料點的「勢力範圍」，因為落於此多邊形之內的任何點，都會離此取樣資料點較近，而離其他取樣資料點較遠。

Hint

在樣式辨識（Pattern Recognition）學科的觀點來看，Voronoi 圖形就是經由 KNNC (K-Nearest-Neighbors Classifiers) 分類方法在 K 等於 1 時所得到的結果，如果在依照不同的類別來對 Vornoi 圖形進行著色，就可以得到 KNNC 的決策邊界（Decision Boundary）。

此外，MATLAB 的 convhull 指令可用於計算一組資料點的最小凸多邊形（Convex Hulls）。例如，我們可用 confhull 指令來計算並顯示 seamount 資料點的最小凸多邊形，如下：

Example 7: 09-內插法/convhull01.m

load seamount.mat plot(x, y, '.'); k = convhull(x, y); hold on, plot(x(k), y(k), 'r'), hold off % 畫出最小凸多邊

另一個類似的指令是 inpolygon，可用於計算一個資料點是否落於一個封閉的多邊形。例如，我們可以先產生一個六邊形，再用 inpolygon 找出位於此六邊形內部的資料點，然後使用不同的顏色來畫出這兩類資料，如下：

Example 8: 09-內插法/inpolygon01.m

theta = linspace(0, 2*pi, 7); xv = cos(theta); yv = sin(theta); x = randn(250,1); y = randn(250,1); in = inpolygon(x, y, xv, yv); plot(xv, yv, 'b', x(in), y(in), 'g.', x(~in), y(~in),'k.'); axis image

---

MATLAB程式設計：進階篇